import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> res = solution.letterCombinations("2");
        System.out.println(res);
    }
}

class Solution {

    Map<Character, Character[]> digit2Letter = new HashMap<>();

    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()) return new ArrayList<>();

        digit2Letter.put('2', new Character[]{'a', 'b', 'c'});
        digit2Letter.put('3', new Character[]{'d', 'e', 'f'});
        digit2Letter.put('4', new Character[]{'g', 'h', 'i'});
        digit2Letter.put('5', new Character[]{'j', 'k', 'l'});
        digit2Letter.put('6', new Character[]{'m', 'n', 'o'});
        digit2Letter.put('7', new Character[]{'p', 'q', 'r', 's'});
        digit2Letter.put('8', new Character[]{'t', 'u', 'v'});
        digit2Letter.put('9', new Character[]{'w', 'x', 'y', 'z'});

        List<String> res = new ArrayList<>();
        backtrack(digits, 0, "", res);
        return res;
    }

    public void backtrack(String digits, int i, String cur, List<String> res){
        if(i == digits.length()){
            res.add(cur);
            return;
        }

        char c = digits.charAt(i);
        for(int j = 0; j < digit2Letter.get(c).length; j++){
            backtrack(digits, i + 1, cur + digit2Letter.get(c)[j], res);
        }
    }
}